import java.util.*;


public class Test {
    /*
    题目 1 ：和为 K 的子数组
     */
    //给你一个整数数组 nums 和一个整数 k
    // 请你统计并返回 该数组中和为 k 的连续子数组的个数 。
    //暴力枚举
    public static int subarraySum1(int[] nums, int k) {
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            for(int j = i; j >=0; j--){
                sum += nums[j];
                if(sum == k){
                    count++;
                }
            }
        }
        return count;
    }
    //这其实跟上面的写法一样的，但我觉得上面的写法可读性更强一点
    public static int subarraySum2(int[] nums, int k) {
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            int j = i;
            int ret = k;
            while(j < nums.length){
                ret -= nums[j++];
                if(ret == 0){
                    count++;
                }
            }
        }
        return count;
    }

    //官方解法：前缀和 + 哈希表 优化
    //pre[i] 表示下标 0 ~ i 的所有元素和，可以表示成 pre[i] == pre[i - 1] + nums[i]
    //那么对于下标 j ~ i 的所有元素之和为 k ，可以表示成 pre[i] - pre[j - 1] == k
    //移项可得： pre[i] - k == pre[j - 1]

    public static int subarraySum(int[] nums, int k) {
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        int pre = 0;
        map.put(0,1);
        for(int i = 0; i < nums.length; i++){
            pre += nums[i];
            if(map.containsKey(pre - k)){
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre,0) + 1);
        }
        return count;
    }

    public static void main1(String[] args) {
        int[] nums = {1,1,1};
        subarraySum(nums,2);
    }

    /*
    题目 2 ：爬楼梯
     */
    //斐波那契数列
    //方法一:递归求解————超出时间限制！
     public int climbStairs1(int n) {
         if(n == 1 || n == 0){
             return 1;
         }
         return climbStairs(n - 1) + climbStairs(n - 2);
     }
    //这个方法竟然叫动态规划
    //第 i 个的元素，跟前面相邻的元素有关
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i = 1; i < n; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    /*
    题目 3 ：移动 0
     */
    //在数组原地操作，让 0 移动至数组末尾，并且其余元素的相对位置不变
    //双指针方法
    //我自己的思路：直接覆盖的话，后面有多少个 0 ，得重新写回去
    //如果每一次都交换的话，后面就不用写 0 了，
     public void moveZeroes1(int[] nums) {
         int j = 0;
         for(int i = 0; i < nums.length; i++){
             if(nums[i] != 0){
                 nums[j++] = nums[i];
             }
         }
         while(j < nums.length){
             nums[j++] = 0;
         }
     }
    //运行时间反而更慢了，囧
    public void moveZeroes(int[] nums) {
        int j = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                swap(nums,i,j);
                j++;
            }
        }
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /*
    题目 4 ：找出数组中所有消失的数字
     */
    //给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内
    // 请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字
    // 并以数组的形式返回结果。
    //自己的思路：哈希表 set ！！
    //把数组的元素放入 set 中去重
    //然后 遍历 1 到 n
    //将 set 中未包含的那个数字添加进 list 中
    //时间复杂度 O(n)
    //空间复杂度 O(n)
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;
        List<Integer> list = new LinkedList<>();
        for(int i = 0; i < n; i++){
            set.add(nums[i]);
        }
        for(int i = 1; i <= n; i++){
            if(!set.contains(i)){
                list.add(i);
            }
        }
        return list;
    }
    //来自官方的优化：
    //利用数组本身来充当哈希表，以此达到空间复杂度 O(1)
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> list = new LinkedList<>();
        for(int num : nums){
            //每一个元素范围在 [1,n]
            //mod n 有两个目的
            //一是：为了得到该元素在数组的下标
            //二是，去除后面 + n的影响，依旧能拿到原本元素在数组中的下标
            int x = (num - 1) % n;
            nums[x] += n;
            //这样一来，以出现元素作为数组下标上的值，都会大于n
        }
        for(int i = 0; i < n; i+=){
            if(nums[i] <= n){
                list.add(i + 1);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[] nums = {4,3,2,7,8,2,3,1};
        findDisappearedNumbers(nums);
    }


}
